package com.arrays.a1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
/**
 * 2022-04-09
 * 全排列46
 */

public class Permute46 {

    public List<List<Integer>> permute(int[] nums) {
        int len=nums.length;
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (len==0){
            return res;
        }
        //实例化栈
        ArrayDeque<Integer> path = new ArrayDeque<>();//ArrayDeque 栈
        boolean[] used = new boolean[len];
        /*递归函数
        depth：深度
        path：已存放的数 栈
        used：已用的数
         */
        dfs(nums,len,0,path,used,res);

        return res;
    }
    //递归逻辑
    private void dfs(int[] nums, int len, int depth, ArrayDeque<Integer> path, boolean[] used, ArrayList<List<Integer>> res) {
        if (depth==len){
            //深度等于数组长
            //将存入path的数拷贝到新的list放入res
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (used[i]){
                continue;
            }
            path.addLast(nums[i]);//添加到最后一个位置
            used[i]=true;

            dfs(nums, len, depth+1,path,used,res);//递归到下一层
            //回溯
            path.removeLast();
            used[i]=false;
        }
    }

    public static void main(String[] args) {
        int[] a ={1,2,3};
        Permute46 pe = new Permute46();
        List<List<Integer>> res = pe.permute(a);
        for (List<Integer> re : res) {
            System.out.println(re);
        }
    }
}

